package leetcode.题库.字符串;

/**
 * 最长回文子串
 *
 * @author yanzhenming
 * @date 2023/3/23  15:50
 */

/**
 * 描述
 *
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串
 */

/**
 * 思路
 *
 * 中心扩展法
 */
public class Solution5 {

    public static void main(String[] args) {
        String s = new String("cbbd");
        System.out.println(longestPalindrome(s));
    }

    public static String longestPalindrome(String s) {
        String res = "";
        int len1, len2, maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            len1 = longestPalindrome(s, i, i);
            len2 = longestPalindrome(s, i, i+1);
            if (len1 > maxLen && len1 > len2) {
                res = s.substring(i -(len1/2), i +(len1/2) + 1);
                maxLen = len1;
            }
            if (len2 > maxLen && len2 > len1) {
                res = s.substring(i - (len2/2) + 1, i + (len2/2) + 1);
                maxLen = len2;
            }
        }
        return res;
    }

    public static int longestPalindrome(String s, int l, int r){
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;r++;
        }
        return r-l-1;
    }
}
